package com.leetcode.周赛.第225场;

/**
 * @author: xiaomi
 * @date: 2021/1/24
 * @description: 5662. 满足三条件之一需改变的最少字符数
 * https://leetcode-cn.com/contest/weekly-contest-225/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
 */
public class B_5662_满足三条件之一需改变的最少字符数 {
    public static void main(String[] args) {
        String a = "aba";
        a = "da";
        a = "aaaaa";
        a = "ace";
//        a = "dcada";
        String b = "caa";
        b = "cced";
        b = "aa";
        b = "abe";
//        b = "d";
        B_5662_满足三条件之一需改变的最少字符数 action = new B_5662_满足三条件之一需改变的最少字符数();
        int res = action.minCharacters(a, b);
        System.out.println("res = " + res);
    }

    /**
     * 只能枚举了
     *
     * @param a
     * @param b
     * @return
     */
    public int minCharacters(String a, String b) {
        int[] aArr = new int[26];
        int aBiggestIndex = 0;
        int aSmallestIndex = 26;
        int aMaxNum = 0;

        int[] bArr = new int[26];
        int bBiggestIndex = 0;
        int bSmallestIndex = 26;
        int bMaxNum = 0;
        for (int i = a.length() - 1; i >= 0; i--) {
            int index = a.charAt(i) - 'a';
            aBiggestIndex = Math.max(index, aBiggestIndex);
            aSmallestIndex = Math.min(index, aSmallestIndex);
            aArr[index]++;
            aMaxNum = Math.max(aMaxNum, aArr[index]);
        }
        for (int i = b.length() - 1; i >= 0; i--) {
            int index = b.charAt(i) - 'a';
            bBiggestIndex = Math.max(index, bBiggestIndex);
            bSmallestIndex = Math.min(index, bSmallestIndex);
            bArr[index]++;
            bMaxNum = Math.max(bMaxNum, bArr[index]);
        }
        //统计完毕，接下来分别尝试不同策略
        int res = Integer.MAX_VALUE;
        //1.a 所有的都小于 b
        int r1 = 0;
        for (int i = 0; i <= aBiggestIndex; i++) {
            r1 += bArr[i];
        }
        int r12 = 0;
        //或者可以改变 a ，让a 所有的都小于 b
        for (int i = bSmallestIndex; i < 26; i++) {
            r12 += aArr[i];
        }
        r1 = Math.min(r1, r12);
        //还可以两边都拆
        //感觉有点动态规划，不太好搞
        int aTempBiggestIndex = aBiggestIndex;
        int bTempSmallestIndex = bSmallestIndex;
        int r13 = 0;
        while (aTempBiggestIndex >= bSmallestIndex) {
            r13 += aArr[aTempBiggestIndex--] + bArr[bTempSmallestIndex++];
        }
        r1 = Math.min(r1, r13);

        //2.b 所有都小于 a
        int r2 = 0;
        for (int i = 0; i <= bBiggestIndex; i++) {
            r2 += aArr[i];
        }
        int r22 = 0;
        for (int i = aSmallestIndex; i < 26; i++) {
            r22 += bArr[i];
        }
        r2 = Math.min(r2, r22);
        int aTempSmallestIndex = aSmallestIndex;
        int bTempBiggestIndex = bBiggestIndex;
        int r23 = 0;
        while (bTempBiggestIndex >= aTempSmallestIndex) {
            r23 += bArr[bTempBiggestIndex--] + aArr[aTempSmallestIndex++];
        }
        r2 = Math.min(r2, r23);

        res = Math.min(r1, r2);

        //3.都相同
        //要么都转为 a 中最多的，要么都转为 b 中最多的，要么转为 重合最多的
        int maxRepeatCount = 0;
        for (int i = 0; i < 26; i++) {
            maxRepeatCount = Math.max(aArr[i] + bArr[i], maxRepeatCount);
        }
        int r3 = a.length() + b.length() - maxRepeatCount;
        return Math.min(res, r3);
    }
}
